package main

import "fmt"
/* 注意偏移量 注意偏移量 注意偏移量 注意偏移量 注意偏移量*/
func main() {

	arr := []int {5,6,3,2,8,7,4,1}

	mergeSort(&arr,0,len(arr)-1)

	for _,value := range arr {
		fmt.Println(value)
	}
}
func mergeSort(arr *[]int,start,end int)  {

	if start >= end {
		return
	}

	middle := start + (end-start)/2

	mergeSort(arr,start,middle)
	mergeSort(arr,middle+1,end)
	merge(arr,start,middle,end)
}
func merge(arr *[]int,start,middle,end int){
	// 开辟一个空间,复制一样的一个数组
	aux := make([]int, end-start+1)
	for i := start; i <= end; i++ {
		aux[i-start] = (*arr)[i]
	}


	i := start
	j := middle+1

	// 遍历arr开始添值
	for k := start; k<= end; k ++{
		// 越界
		if i > middle {
			(*arr)[k] = aux[j-start]
			j ++
		}else if j > end {
			(*arr)[k] = aux[i-start]
			i++
		}else if aux[i-start] < aux[j-start] { // 两边排好序的数组比较
			(*arr)[k] = aux[i-start]
			i ++
		}else {
			(*arr)[k] = aux[j-start]
			j++
		}
	}
}
